package practice_2025_9.pracitce_9_2;

import java.util.ArrayList;
import java.util.List;

class Solution1 {
    List<String> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    /**
     * 复原 IP 地址
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {
        // 返回所有可能的有效 ip 地址
        // 划分为 4 个整数, 每个整数位于 0 - 255 之间
        int len = s.length();
        // 无法构造有效 ip
        if (len < 4) {
            return res;
        }
        // 要将字符串分为 4 份 -> 递归
        dfs(0, len, s);
        return res;
    }

    public void dfs(int index, int n, String str) {
        // System.out.println(list);
        // 递归出口
        if (list.size() > 4) {
            return;
        }
        // 遍历完成
        if (index >= n) {
            // 存在有效 ip
            if (list.size() == 4) {
                StringBuilder stringBuilder = new StringBuilder();
                for(int i = 0; i < 4; i++) {
                    stringBuilder.append(list.get(i)).append(".");
                }
                res.add(stringBuilder.substring(0, stringBuilder.length() - 1));
                // System.out.println(stringBuilder.toString());
            }
            return;
        }

        // 继续递归
        // 当前字符为 0
        if (str.charAt(index) == '0') {
            list.add(0);
            // 递归
            dfs(index + 1, n, str);
            // 回溯
            list.remove(list.size() - 1);
        } else {
            // 枚举每一种可能
            int addr = 0;
            for(int i = index; i < n; i++) {
                addr = addr * 10 + (str.charAt(i) - '0');
                if (addr > 0 && addr <= 255) {
                    list.add(addr);
                    dfs(i + 1, n, str);
                    // 回溯
                    list.remove(list.size() - 1);
                } else {
                    break;
                }
            }
        }
    }
}